#include<iostream>
using namespace std;
//class A {
//public:
//	virtual void func() = 0;
//	int a = 0;
//	static int b;
//};
//int A::b = 0;
//int main()
//{
//	return 0;
//}


class Solution {
public:
    long long minIncrementOperations(vector<int>& nums, int k) {
        // int n=nums.size();
        // long long memo[n][3];
        // memset(memo,-1,sizeof(memo));
        // function<long long(int i,int j)>dfs=[&](int i,int j)->long long{
        //     if(i<0) return 0;
        //     if(memo[i][j]!=-1) return memo[i][j];
        //     long long res=dfs(i-1,0)+max(k-nums[i],0);
        //     if(j<2) res=min(res,dfs(i-1,j+1));
        //     return memo[i][j]=res;
        // };
        // return dfs(n-1,0);

        // int n=nums.size();
        // long long f[n+1][3];
        // memset(f,0,sizeof(f));
        // for(int i=0;i<n;i++){
        //     for(int j=0;j<3;j++){
        //         f[i+1][j]=f[i][0]+max(k-nums[i],0);
        //         if(j<2) 
        //             f[i+1][j]=min(f[i+1][j],f[i][j+1]);
        //     }
        // }
        // return f[n][0];

        long long f[3] = { 0 };
        for (auto& x : nums) {
            long long new_f = f[0];
            for (int j = 0; j < 3; j++) {
                f[j] = new_f + max(k - x, 0);
                if (j < 2)
                    f[j] = min(f[j], f[j + 1]);
            }
        }
        return f[0];
    }
};

class Solution {
public:
    int maximumPoints(vector<vector<int>>& edges, vector<int>& coins, int k) {
        int n = coins.size();
        vector<vector<int>>g(n);
        for (auto& e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        int memo[n][14];
        memset(memo, -1, sizeof(memo));
        function<int(int, int, int)>dfs = [&](int i, int j, int fa)->int {
            if (memo[i][j] != -1) return memo[i][j];
            int res1 = (coins[i] >> j) - k;
            int res2 = (coins[i] >> (j + 1));
            for (int x : g[i]) {
                if (x == fa) continue;
                res1 += dfs(x, j, i);
                if (j < 13)//1e4>>14==0
                    res2 += dfs(x, j + 1, i);
            }
            return memo[i][j] = max(res1, res2);
        };
        return dfs(0, 0, -1);
    }
};